Hard disk drives (“disks”) are common data storage devices used in conjunction with computers. Computers typically store data either on locally attached disks or on a remote data storage server computer which has its own locally attached disks. Disks, like other electronic devices, are prone to occasional failures which can result in a loss of access to the data on the disk. A technique for protecting data against the failure of a disk is to combine several disks into a Redundant Array of Inexpensive (or Independent) Disks (RAID).
RAID levels define a relationship between data and disks. A collection of disks which implement a RAID level is conventionally referred to as a RAID array. Different RAID levels may involve mirroring data between disks, striping data across disks, or striping data and parity information across disks. RAID arrays of RAID levels 3, 4 and 5 involve striping data across all of the disks of the array, which may contain many thousands of equally sized stripes, and also involves storing parity information in the array. Each disk contributes the same amount of storage space for a particular stripe, referred to as a block. The size of a block, or block size, is usually constant throughout a RAID array and is usually defined when the RAID array is created. Thus, a stripe has a total storage space of the block size times the difference between the number of disks in the RAID array and the number of parity blocks per stripe. One or more blocks of each stripe are reserved for storing parity information. Parity information is mathematically derived from the data in other blocks of the stripe, conventionally by performing a logical “exclusive or” (XOR) operation on the data within the stripe. In the event of a disk failure, the data from any particular block on the disk that failed can be recreated by performing the XOR operation on the data and parity information in the remaining blocks of the stripe to recreate the lost data, and the recreated data is then typically written to a spare disk associated with the RAID array. In this manner the data from the failed disk is recreated on the spare disk to maintain the fully functional RAID array.
One way of distributing parity blocks throughout a RAID array is to keep all of the parity blocks on a single dedicated parity disk, as is the case in RAID levels 3 and 4. Since parity information is usually calculated and written to disk every time data is written to an array, a dedicated parity disk usually incurs a write operation whenever data is written to another disk of the array. Although the use of RAID levels 3 or 4 may be desirable in certain situations, continual write operations to the dedicated parity disk can result in the parity disk becoming a performance bottleneck. Another way of distributing parity blocks throughout a RAID array is to distribute the parity blocks evenly across all of the disks in the array, as is the case in RAID level 5. Arrays with striped parity generally have better read and write performance than arrays with dedicated parity disks, since no particular disk is written to every time data is written to the array, which can result in a higher data throughput compared to RAID levels 3 and 4.
A RAID array is usually controlled by a RAID controller, which may be implemented in hardware, such as a RAID controller card, or in software, such as a RAID aware operating system. The RAID controller presents the data blocks on the RAID array to the operating system of the computer to which the array is attached as a logical address space. A logical address space is typically a sequential series of numbers, or addresses, starting from 1 and continuing to the maximum number of data blocks in the array. The RAID controller performs any necessary conversion to determine which physical data block on a particular disk corresponds to which address within the logical address space of the array, and vice versa.
Creating a distributed parity disk array having distributed parity, such as a RAID level 5 array, on a particular number of disks involves designating certain blocks of the disks for use as parity blocks and certain other blocks of the disks for use as data blocks. A simple way of designating data and parity blocks in an array of N disks is to assign the parity block of the first stripe to the first disk, assign the parity block of the second stripe to the second disk, and so on until the parity block of the Nth stripe is assigned to the Nth disk. The data and parity blocks for the remaining stripes are then assigned to blocks of the disks according to the pattern defined by the first N stripes. Similarly, a dual parity array on N disks can be created by assigning the parity blocks for the first stripe to the first and second disks, then assigning the parity blocks for the second stripe on the second and third disks, and so on until the parity blocks for the Nth stripe are assigned to the first and last disks. The pattern defined by the allocation of parity and data blocks for the first N stripes is then repeated for the remaining stripes.
Partially as a result of continued business operations and increased governmental regulation, most businesses have data storage requirements which are continually increasing. A system administrator who manages a data storage server typically adds another RAID array to the data storage server when the existing RAID array(s) are running out of available data storage space. Allocating a new RAID array to accommodate increasing data storage requirements is typically less than ideal because the new RAID array may have much more data storage space than will be needed or used in the immediate future. A more ideal solution is to add disks to an existing RAID array as needed to meet increasing data storage requirements.
Most RAID controllers can create or delete a striped distributed parity RAID array, but are not typically functional to expand the array by adding a new disk once the array has been created. One of the challenges involved in adding a new disk to an existing array is determining how to redistribute the parity blocks across the disks of the array evenly (i.e., each disk has substantially the same number of parity blocks). It is desirable to minimize assigning parity blocks to locations which were previously data blocks while redistributing the parity blocks in order to minimize the amount of data blocks that must be copied before new parity information is calculated. Redistributing parity blocks is especially challenging in distributed parity RAID arrays having dual or higher order parity, since care must be taken to avoid attempting to assign two parity blocks from the same stripe to the new disk.
These and other considerations have led to the evolution of the present invention.